1. Field of the Invention
The present invention relates generally to a system and method for building a knowledge base for use in a knowledge based or expert computer system. More specifically, the present invention relates to a system and method for building a Rete pattern matching network of rules for use in a knowledge based computer system.
2. Related Art
Knowledge bases for expert systems operating on computers are typically composed of rules. These rules are commonly expressed in the form of IF-THEN statements. The IF portion of the rule represents a collection of conditions (tests against objects in the system) forming patterns.
The matching of a large collection of patterns to a large collection of objects is one operation of an inference engine. An inference engine is the reasoning component in artificial intelligence and expert systems. Inference engines typically contain three components or methods: (1) matching a collection of objects to a given rule, (2) selecting a rule from a list of rules whose conditions are completely matched by objects, and (3) firing of the selected rule.
The most time consuming phase in an inference engine is the matching process. For example, consider a system and method with a 1000 objects and a 1000 rules, where each rule has three conditions. In a very simple implementation scheme, each rule is compared against all objects. This leads to over a trillion match operations for each execution cycle.
The Rete pattern matching algorithm is a complex algorithm that can achieve the result of this example with only a small fraction of the work (that is, much fewer than a trillion match operations). The Rete pattern matching algorithm is described in C. L. Forgy, "RETE: A FAST ALGORITHM FOR THE MANY PATTERN/MANY OBJECT PATTERN MATCH PROBLEM," Artificial Intelligence, Vol. 19, pp. 17-37 (1982); and C. L. Forgy, MEASUREMENTS ON PRODUCTION SYSTEMS, Department of Computer Science, Carnegie-Mellon University, Pittsburgh, Pa. (1983). These references are hereby incorporated by reference, in their entirety, into this specification. Note that the Rete pattern matching algorithm will be described only to the extent necessary for an understanding of the problem(s) solved by the present invention.
The Rete pattern matching algorithm implements a "divide and conquer" strategy to the matching component or method. The conditions that make up a given rule are tested. Failure of one condition prevents testing of subsequent conditions. To perform the matching the Rete pattern matching algorithm uses an augmented discrimination network (referred herein as a Rete network) compiled from the premise of the rule. Each object is first tested against conditions that involve only that object. Objects which pass these tests are then joined with other objects to perform tests requiring multiple objects. Collections of objects which pass all tests become candidates for selection and firing.
The Rete network comprises a network of connected nodes. These nodes comprise either a root node(s), alpha node(s), beta node(s), and node(s), beta--not node(s), and--not node(s), terminal node(s) and, gamma node(s). There is one root node for every object type.
Root nodes represent the entry points for objects to be tested. Root nodes broadcast the objects to the successor nodes in the network based on their object type.
Alpha nodes represent intra-element tests. Intra-element tests perform tests against a single object. Intra-element tests may relate to whether the attributes of an object have a constant value as specified in the rule. Intra-element tests may also relate to whether the attributes of an object are related to a constant by a predicate. Intra-element tests may further relate to whether two attributes of the same object match under a specified relation. These tests may be performed on variables which are negatively quantified in the rule premise. These tests may also be performed on variables which are positively quantified. That is, they may be used to verify the non-existence of a variable as well as the existence of a variable.
Beta nodes and beta--not nodes represent inter-element tests. Unlike intra-element tests, inter-element tests examine attributes of multiple data objects. These tests determine whether there is some relationship between two or more data objects. Beta nodes are used to test sets of data objects which are either (1) purely negatively quantified, or (2) purely positively quantified. Tests involving a combination of positively quantified and negatively quantified variables are referred to a mixed quantification tests. These are implemented in the Rete network by beta--not nodes. Gamma nodes are a variation of beta nodes. Like beta nodes, these nodes perform inter-element tests. However, unlike beta nodes, these nodes receive all of their input from one source: beta nodes have a left input and a right input, while gamma nodes only have a left input.
All inter-element tests require that several data objects be brought together so that they are available for testing at one point. Since beta nodes have two inputs, they help to combine objects. Sometimes, however, all of the objects are already available at one point (perhaps a prior beta node, for example). If this one point can serve as an input for the inter-element test, the second input is superfluous. Thus, some conventional systems distinguish between gamma and beta nodes to accommodate this variant case.
AND nodes are used to create combinations of objects for later testing by subsequent nodes. These nodes perform no testing. They merely facilitate the merging of data objects. And--not nodes are a variant example of an AND node. These join together the results of positively quantified variable tests with results of negatively quantified variable tests. When taken in conjunction with the alpha, beta, and gamma tests described above, the and--not node implements the semantics of non-existence testing.
Terminal nodes represent the bottom of the Rete network for a given rule. Each rule has only one terminal node.
To avoid performing the same tests repeatedly, the Rete network employs memory nodes. Memory nodes store the result of a match with an object as a state within the network. These nodes are termed alpha memory nodes and beta memory nodes. To implement the memory nodes, the objects that are passed between nodes in the network are called "tokens", which comprise a tag and a list of objects. The tag can be either a +, indicating that something has been added to the knowledge base, or a -, indicating that something has been removed from the knowledge base. The list of objects associated with a token corresponds to the permutation of those objects that the system is trying to match or has already matched against a subsequence of objects in the rule premise.
In operation, whenever the token arriving at the input of an alpha node satisfies the associated test, it is passed on to the successors of the alpha node. If the token does not satisfy the test, it is not passed on to the successors. If an object satisfies all intra-element tests (note it may not, as yet, satisfy all the inter-element tests), the object is said to partially match a rule. Tokens corresponding to objects that partially match a condition in the rule premise are stored in the alpha memory node. If two objects, in the same or different rules, have exactly the same tests for a successful partial match, the network shares alpha memory node for the two.
When a token is distributed to the left input of a beta node, the beta node compares the incoming token to each token stored in the alpha memory node associated with its right ancestor alpha node. For every right-token which is consistent with the left-token, a new token is constructed and stored in the successor beta memory node. The token is then passed to the successor nodes. The new token has the same tag as that of the left-token, and the list of objects is the compilation of objects for the left and right tokens.
Whenever a token with a + tag flows into a terminal node, it adds an instantiation (corresponding to the token) of the associated rule into the conflict set. The arrival of a token with a - tag leads to the deletion of the corresponding rule instantiation from the conflict set.
As should be appreciated, only changes made to the knowledge base by the most recent rule firing have to be processed every cycle. These changes "filter" through the network, and where relevant, the state stored in the network is updated. This is a significant attribute of the Rete pattern matching algorithm. The output of the network comprises a specification of bound variables, (bindings, matched objects) to the conflict set.
The Rete network was first implemented using an OPS5 (computer language) based computer system. The OPS5 system is described in C. L. Forgy, OPS5 USERS MANUAL, Department of Computer Science, Carnegie-Mellon University (1981). This reference is hereby incorporated by reference, in its entirety, into this specification.
In an OPS5 based computer system, a user must format the left hand side (LHS), or premise, of a rule in conjunctive form. In other words, the Rete network can only process rules that are expressed in conjunctive form. A typical OPS5 rule named p1 is expressed using the following syntax:
______________________________________ (p p1 (C1 .uparw.attr1 &lt;x&gt; .uparw.attr2 12) (C2 .uparw.attr1 15 .uparw.attr2 &lt;x&gt;) - (C3 .uparw.attr1 &lt;x&gt;) (remove 2)) ______________________________________
Rule p1 has three conditions in its LHS. These conditions are identified by the sets of closed parentheses.
The first condition (the first line of the rule) has three separate tests. The first test corresponds to whether an object is of the type C1. The second test corresponds to whether an object of the type C1 has an attribute .uparw.attr1 and some value &lt;x&gt;. Any value will match the variable x. (Note that the implications of specifying a value with a variable is discussed below.) The third test corresponds to whether an object of the type C1 has the attribute .uparw.attr2 with a value equal to 12.
The second condition (the second line of the rule) also has three separate tests. The first test corresponds to whether an object is of the type C2. The second test corresponds to whether an object of the type C2 has the attribute .uparw.attr1 with a value equal to 15. The third test corresponds to whether an object of the type C2 has the attribute .uparw.attr2 with a value &lt;x&gt;.
The third condition (the third line of the rule) has only two separate tests. Note that the condition is negated (see the -). The first test corresponds to whether an object is of the type C3. The second test corresponds to whether an object of the type C3 has the attribute .uparw.attrI and a value &lt;x&gt;.
Rule p1 is fired if there is an object in the computer based system and method that satisfies the first condition and there is an object that satisfies the second condition and there is an object in that satisfies the third condition. Note that this and relationship between the three example conditions denotes a conjunctive relationship.
It should be noted that in rule 1, the variable x is specified in one test for each condition: .uparw.attr1 of object type C1 in the first condition; .uparw.attr2 of object type C2 in the second condition; and, .uparw.attr1 of object type C3 in the third condition. The consequence of the common specification of variable x is that for the rule to fire, the architecture of an OPS5 language computer system requires that objects C1, C2, and C3 and their corresponding attributes (.uparw.attr1, .uparw.attr2, .uparw.attr1, respectively) have the same value. In an OPS5 based computer system, this is the only way to test whether the attributes of different objects are equal.
It should be understood that the Rete network building architecture of the OPS5 system does not allow the user to test in one condition whether the attributes of different objects are the same: the user must incorporate the test when the object type is first defined. As is discussed below, this limitation is a significant drawback.
It should also be understood that the user must specify all intra-element tests for a given object type when the object type is first defined. As is discussed below, the above constraint is likewise a significant disadvantage of the OPS5 Rete network building architecture.
The OPS5 system builds the Rete network by examining in sequence each condition of the rule looking for intra-element tests: a test against a single object. For each condition the network compiler chains together test nodes that check for intra-element tests of a specific object type (there may be several intra-element tests for a given condition, and thus for an object). The OPS5 system builds an alpha node for each of the intra-element tests in the exact order in which the user has written the rule.
Once the network compiler has finished with the intra-element tests, it re-examines each condition of the rule and adds nodes that check for inter-element tests. An OPS5 based system builds Beta nodes first. The Beta nodes are likewise built in the exact order as written by the user. The OPS5 system then builds beta--not nodes. The beta--not nodes are also built in the exact order written by the user. In an OPS5 system, the right input of a beta node or a beta--not mode always comes from an alpha node, while its left input can come from an alpha node or a beta node.
The OPS5 compiler than adds a terminal node for each rule.
As may be apparent, the OPS5 system uses a "high control" architecture. The term "high control" means a system and method in which the user has complete control over the resultant Rete network structure. A high control system allows a user with a high degree of familiarity with the constraints of OPS5 to write the rules so that an optimal Rete network can be constructed. The more optimal the Rete Network, the faster the matching process. These users are sometimes referred to as "power users." A user less familiar with this high control architecture is likely to encounter significant problems when building an efficient Rete network.
As discussed previously, one significant problem with the OPS5 Rete network building architecture relates to its flexibility to process the specification of tests about an object within a rule premise. In an OPS5 system, the user must specify all tests that relate to a specific object (whether intra-element or inter-element tests) when the object type is first defined. The OPS5 architecture necessitates that all tests about an object be grouped in one condition. The OPS5 architecture is very inflexible.
The above constraint prevents a user from writing arbitrary tests about an object or inter-related tests about several objects. The OPS5 architecture dictates the way a user can think about and express a rule. This is a significant limitation of the OPS5 system.
Another problem with the OPS5 architecture relates to the ability to use disjunctions. An OPS5 system does not recognize disjunctions (that is, OR related conditions): the Rete network is a conjunction process only. In other words, the Rete network is success oriented. Objects either pass or do not pass a given test. There is no middle ground for passing under certain cases but not others. The use of a disjunction implies the use of this "middle" ground. Hence, the Rete network cannot be regarded as intrinsically disjunctive. In OPS5, the user must build two separate rules. Specifically, the user must build one rule for each clause of the disjunction.
Another significant problem with the OPS5 architecture relates to the ability of the user to write a negated rule(s). An OPS5 system does not recognize a complex negated premise. A user is forced to write the rule in a positively framed statement.
Another problem with the OPS5 architecture relates to the requirement that to perform the action (RHS) part of a rule in a Rete based system, the objects referenced on the RHS must be bound to the LHS of the rule. In an OPS5 based system, the user must make sure that the object being acted on in the RHS of the rule is referenced in the LHS of the rule. Failure to meet this requirement may result in a system malfunction.
While the above describes the standard Rete network processing, other implementations and enhancements to Rete processing are possible. By way of example only, modifications to Rete network processing are described in M. I. Schor et al.. Advances In Rete Pattern Matching, IBM T. J. Watson Research Center, Yorktown Heights, N.Y. (1986). This reference is hereby incorporated by reference in its entirety.
Another augmentation to the Rete pattern matching algorithm is the Treat Algorithm. The Treat algorithm is described in Miranker, Daniel P., "Treat: A Better Way for A1 Production Systems," Proceedings of Sixth National Conference on Artificial Intelligence, Seattle, Wash., July 13-17, 1987, pp. 42-47. This reference is hereby incorporated by reference in its entirety. As described therein, the major difference is that the Treat algorithm does not save partial results in the network. This has the advantage of using less memory than is used by the Rete algorithm.